package lbj.cyw.dp;
/*
* 312. 戳气球
* 最后一步: 开区间(-1,n)内最后一个气球k被戳破时所能获得的最大价值是多少? (就不用管前面怎么戳破的, 就只管最后一步)
* 子问题 : 开区间(-1,k)所能获得最大价值是多少?
*       dp[i][j]表示开区间 (i,j)内所能获得的最大价值
* 转移方程: dp[i][j]=dp[i][k]+val[i]*val[k]*val[j]+dp[k][j]
*
* */
public class MaxCoins312 {
    public int maxCoins(int[] nums){
        int n=nums.length;
        int[] tmp=new int[n+2];
        tmp[0]=1;
        tmp[n+1]=1;
        for (int i = 1; i <= n; i++) {
            tmp[i]=nums[i-1];
        }
        int[][]  dp=new int[n+2][n+2];
        // len表示 区间 长度
        for(int len=3;len<=n+2;len++){
            //i表示区间 左边界
            for(int i=0;i<=n+2-len;i++){
                int res=0;
                for(int k=i+1;k<i+len-1;k++){
                    int left=dp[i][k];
                    int right=dp[k][i+len-1];
                    res=Math.max(tmp[i]*tmp[k]*tmp[i+len-1]+left+right,res);
                }
                dp[i][i+len-1]=res;
            }
        }
        return dp[0][n+1];
    }
}
